package swordoffer.offer26;

public class IsSubStructure {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        //当A节点与B节点值相等时，对这个节点的左、右子树进行递归，判断
//        if (A.val == B.val && (isContain(A.left, B.left) && isContain(A.right, B.right))) {
//            return true;
//        }

        //利用isContain()函数来判断A是否包含B，利用isSubStructure()对A的左、右进行遍历，任意一个返回true即是B是A的子结构
        //如果B是A的子结构，1. B就是A树 2. B树是A左子树的子结构 3. B树是A树右子树的子结构
        return isContain(A,B)||isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    /**
     * 判断树A是否包含树B；A、B节点是同步进行的
     *
     * @param A 二叉树A
     * @param B 二叉树B
     * @return 返回是否包含的结果
     */
    public boolean isContain(TreeNode A, TreeNode B) {
        if (A == null && B == null) {
            return true;
        }
        //因为是包含关系，所以B为空说明B已经被访问完毕，是A的子结构
        if (B == null) {
            return true;
        }
        //当A为空时，B还不是空，或者两棵树对应节点的值不相同，就说明B不是A的子结构。
        if (A == null || A.val != B.val) {
            return false;
        }
        //如果上面的条件都为满足，则继续递归左右
        return isContain(A.left, B.left) && isContain(A.right, B.right);
    }
}
